//
// Created by Cammy on 2024/5/8.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Stack.c"

void PrintArray(int *arr, int n) {
    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void Swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

//  假设都用升序来讲，降序就是反过来

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————


// 冒泡排序
/*
 * TODO:冒泡排序时间复杂度 O(N^2)
 *          最好情况 O(N)
 *
 * 跟直接插入排序谁更好？ ==  直接插入排序
 */
void BubbleSort(int *arr, int n) {
    int flag;
    for (int i = 0; i < n; ++i) {
        flag = 0;
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                Swap(&arr[j], &arr[j + 1]);
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————


// 插入排序
/**
 *  TODO：时间复杂度是多少？O(N^2)
 *       什么情况下最坏？逆序
 *       什么情况下最好？顺序有序
 *       最好情况:O(N)
 */
void InsertSort(int *arr, int n) {
    // [0,end] 有序 end+1位置的值插入[0,end]，让[0,end+1]有序
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = arr[end + 1];
        while (end >= 0) {
            if (arr[end] > tmp) {
                arr[end + 1] = arr[end];
                end--;
            } else {
                break;
            }
        }
        arr[end + 1] = tmp;
    }
}

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————


// 希尔排序
/*
 * 直接插入排序的基础上的优化
 * 1.先进行预排序，让数组接近有序
 * 2.直接插入排序
 *
 * 对组间为gap的预排序，gap由大变小
 * gap越大，大的数可以越快到后面，小的数可以越快到前面，越不接近有序
 * gap越小，越接近有序
 *
 * TODO：时间复杂度 O(N*logN) or O(N*log3N)[以3为底的对数]
 */
void ShellSort(int *arr, int n) {
    int gap = n;
    while (gap > 1) {
        gap /= 2;

        // 把间隔为gap的多组数据同时排序
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0) {
                if (arr[end] > tmp) {
                    arr[end + gap] = arr[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————


// 直接选择排序
/*
 * TODO:时间复杂度 0(N^2) 效率最差
 *      直接选择排序，时间复杂度O(N*N)
 *      很差，因为最好情况也是O(N*N)
 */
void SelectSort(int *arr, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int mini = begin, maxi = end;
        for (int i = begin; i < end; i++) {
            if (arr[i] < arr[mini]) {
                mini = i;
            }
            if (arr[i] > arr[maxi]) {
                maxi = i;
            }
        }
        Swap(&arr[begin], &arr[mini]);
        if (begin == maxi)
            maxi = mini;
        Swap(&arr[end], &arr[maxi]);
        ++begin;
        --end;
    }
}

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————


/**
 * 堆排序：
 *      堆的两个特性：
 *          结构性：用数组表示的完全二叉树
 *          有序性：任一节点的关键字是其子树所有节点的最大值（或最小值）
 *              ⚪ 大顶堆：树中所有的父亲都大于等于孩子
 *              ⚪ 小顶堆：树中所有的父亲都小于等于孩子
 *
 * 求左右孩子节点
 *      leftChild = parent * 2 + 1
 *      rightChild = parent * 2 + 2
 * 求父节点
 *      parent = (child - 1) / 2
 */
// 向下调整算法
void AdjustDown(int *arr, int n, int root) {
    int parent = root;
    int child = parent * 2 + 1; // 默认是左孩子
    while (child < n) {
        // 1.选出左右孩子中大的那一个
        if (child + 1 < n && arr[child + 1] > arr[child]) {
            child += 1;
        }
        if (arr[child] > arr[parent]) {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}


void HeapSort(int *arr, int n) {
    // 建堆 O(N)
    /*
     *  TODO:建堆的时间复杂度 O(N)
     */
    for (int i = (n - 1 - 1) / 2; i >= 0; --i) {
        AdjustDown(arr, n, i);
    }

    // 排升序，建大堆
    /**
     * 如果是建小堆，最小数在堆顶，已经被选出来了。
     * 那么在剩下的数中再去选数，但是剩下树结构都乱了。
     * 需要重新建堆，才能选出下一个数，建堆的复杂度是O(N)。
     * 虽然不是不可以，但是堆排序就没有效率优势了。
     */
    int end = n - 1;
    while (end > 0) {
        Swap(&arr[0], &arr[end]);
        AdjustDown(arr, end, 0);
        --end;
    }

}

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————


// 快速排序
/**
 * 挖坑填数
 *
 * TODO：时间复杂度 O(N*logN)
 *      什么情况下最坏？有序或者逆序的时候和直接插入排序一样 时间复杂度是O(N^2)
 *      优化：三数取中 -> 解决快排效率最坏的情况
 */
// TODO：三数取中
int getMidIndex(int *arr, int l, int r) {
    int mid = (l + r) >> 1;// 右移(>>)一位相当于÷2（左移(<<)一位相当于×2）
    if (arr[l] < arr[mid]) {
        if (arr[mid] < arr[r]) {
            return mid;
        } else if (arr[r] < arr[l]) {
            return l;
        } else {
            return r;
        }
    } else // arr[l] > arr[mid]
    {
        if (arr[mid] > arr[r]) {
            return mid;
        } else if (arr[l] > arr[r]) {
            return r;
        } else
            return l;
    }
}

void QuickSort(int *arr, int left, int right) {
    if (left >= right)
        return;

    // TODO：三数取中
    int index = getMidIndex(arr, left, right);
    Swap(&arr[left], &arr[index]);

    int begin = left, end = right;
    int pivot = begin; // 初始化将第一个位置为坑位
    int key = arr[begin];

    // 单趟排序 O(N)
    while (begin < end) {
        // 右边找小，放到左边
        while (arr[end] >= key && begin < end) {
            end--;
        }
        // 小的放到左边的坑里，自己形成新的坑
        arr[pivot] = arr[end];
        pivot = end;

        // 左边找大，放到右边
        while (arr[begin] <= key && begin < end) {
            begin++;
        }
        // 大的放到右边的坑里，自己形成新的坑
        arr[pivot] = arr[begin];
        pivot = begin;
    }

    pivot = begin;
    arr[pivot] = key;

    // [left,pivot-1] pivot [pivot+1,right]
    // TODO：分而治之 -> 让左区间和右区间有序
    // QuickSort(arr, left, pivot - 1);
    // QuickSort(arr, pivot + 1, right);

    // 小区间优化（其实效果不明显）
    if ((pivot - 1) - left > 10) {
        QuickSort(arr, left, pivot - 1);
    } else {
        InsertSort(arr, (pivot - 1) - left + 1);
    }

    if (right - (pivot + 1) > 10) {
        QuickSort(arr, pivot + 1, right);
    } else {
        InsertSort(arr + pivot + 1, right - (pivot + 1) + 1);
    }
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


// TODO:挖坑法
int PartSort1(int *arr, int left, int right) {
    // TODO：三数取中
    int index = getMidIndex(arr, left, right);
    Swap(&arr[left], &arr[index]);

    int begin = left, end = right;
    int pivot = begin; // 初始化将第一个位置为坑位
    int key = arr[begin];

    // 单趟排序 O(N)
    while (begin < end) {
        // 右边找小，放到左边
        while (arr[end] >= key && begin < end) {
            end--;
        }
        // 小的放到左边的坑里，自己形成新的坑
        arr[pivot] = arr[end];
        pivot = end;

        // 左边找大，放到右边
        while (arr[begin] <= key && begin < end) {
            begin++;
        }
        // 大的放到右边的坑里，自己形成新的坑
        arr[pivot] = arr[begin];
        pivot = begin;
    }

    pivot = begin;
    arr[pivot] = key;

    return pivot;
}

// TODO:左右指针法
int PartSort2(int *arr, int left, int right) {
    // TODO：三数取中
    int index = getMidIndex(arr, left, right);
    Swap(&arr[left], &arr[index]);

    int begin = left, end = right;
    int keyIndex = begin;

    // 单趟排序 O(N)
    while (begin < end) {
        // 右边找小
        while (arr[end] >= arr[keyIndex] && begin < end) {
            end--;
        }

        // 左边找大
        while (arr[begin] <= arr[keyIndex] && begin < end) {
            begin++;
        }

        Swap(&arr[begin], &arr[end]);
    }

    Swap(&arr[begin], &arr[keyIndex]);

    return keyIndex;
}

// TODO:前后指针法
int PartSort3(int *arr, int left, int right) {
    int index = getMidIndex(arr, left, right);
    Swap(&arr[left], &arr[index]);

    int keyIndex = left;
    int prev = left, cur = left + 1;
    while (cur <= right) {
        if (arr[cur] < arr[keyIndex] && ++prev != cur) {
//            ++prev; // 在判断里面优化了
            Swap(&arr[cur], &arr[prev]);
        }
        ++cur;
    }

    Swap(&arr[prev], &arr[keyIndex]);
    keyIndex = prev;
    return keyIndex;
}

void newQuickSort(int *arr, int left, int right) {
    if (left >= right)
        return;

    // TODO:挖坑法
//    int keyIndex = PartSort1(arr, left, right);
    // TODO:左右指针法
//    int keyIndex = PartSort2(arr, left, right);
    // TODO:前后指针法
    int keyIndex = PartSort3(arr, left, right);

    // 小区间优化（其实效果不明显）
    if ((keyIndex - 1) - left > 10) {
        QuickSort(arr, left, keyIndex - 1);
    } else {
        InsertSort(arr, (keyIndex - 1) - left + 1);
    }

    if (right - (keyIndex + 1) > 10) {
        QuickSort(arr, keyIndex + 1, right);
    } else {
        InsertSort(arr + keyIndex + 1, right - (keyIndex + 1) + 1);
    }
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// 非递归的快速排序
/**
 * 递归的缺陷：
 *      栈帧深度太深，栈空间不够，可能会溢出
 * 递归改非递归：
 *      1.直接改循环（简单）
 *      2.借助数据结构栈模拟递归过程（复杂一点）
 */
// TODO:挖坑法
int PartSortNoR(int *arr, int left, int right) {

    int begin = left, end = right;
    int pivot = begin; // 初始化将第一个位置为坑位
    int key = arr[begin];

    // 单趟排序 O(N)
    while (begin < end) {
        // 右边找小，放到左边
        while (arr[end] >= key && begin < end) {
            end--;
        }
        // 小的放到左边的坑里，自己形成新的坑
        arr[pivot] = arr[end];
        pivot = end;

        // 左边找大，放到右边
        while (arr[begin] <= key && begin < end) {
            begin++;
        }
        // 大的放到右边的坑里，自己形成新的坑
        arr[pivot] = arr[begin];
        pivot = begin;
    }

    pivot = begin;
    arr[pivot] = key;

    return pivot;
}

void QuickSortNoR(int *arr, int n) {
    Stack stack;
    StackInit(&stack);
    // 栈里面需要的区间需要被单躺分割排序

    StackPush(&stack, n - 1); // 入右半区间
    StackPush(&stack, 0); // 入左半区间

    while (!StackEmpty(&stack)) {
        int left = StackTop(&stack);
        StackPop(&stack);

        int right = StackTop(&stack);
        StackPop(&stack);

        int keyIndex = PartSortNoR(arr, left, right);
        // [left,keyIndex-1] keyIndex [keyIndex+1,right]

        if (keyIndex + 1 < right) {
            StackPush(&stack, right);
            StackPush(&stack, keyIndex + 1);
        }

        if (left < keyIndex - 1) {
            StackPush(&stack, keyIndex - 1);
            StackPush(&stack, left);
        }
    }

    StackDestroy(&stack);
}

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

// 归并排序
/**
 * 假设 左半区间有序，右半区间有序，则一次对比取小的放在新的临时数组
 *
 * TODO：时间复杂度 O(N*logN)
 *      归并排序也叫做外排序
 *
 *          使用场景：假设10G数据放到硬盘中，要排序，怎么排？
 *               归并排序，它可以对文件中的数据进行排序
 */
void _MergeSort(int *arr, int l, int r, int *_arr) {
    if (l >= r)
        return;

    int mid = (l + r) >> 1;
    // 假设[l,mid][mid+1,r]有序就可以归并了
    // 分解
    _MergeSort(arr, l, mid, _arr);
    _MergeSort(arr, mid + 1, r, _arr);

    // 归并
    int begin1 = l, end1 = mid;
    int begin2 = mid + 1, end2 = r;
    int index = l;
    while (begin1 <= end1 && begin2 <= end2) {
        if (arr[begin1] < arr[begin2]) {
            _arr[index++] = arr[begin1++];
        } else {
            _arr[index++] = arr[begin2++];
        }
    }

    while (begin1 <= end1) {
        _arr[index++] = arr[begin1++];
    }

    while (begin2 <= end2) {
        _arr[index++] = arr[begin2++];
    }

    // 拷贝回去
    for (int i = l; i <= r; ++i) {
        arr[i] = _arr[i];
    }
}

void MergeSort(int *arr, int n) {
    int *_arr = (int *) malloc(sizeof(int) * n);
    _MergeSort(arr, 0, n - 1, _arr);
    free(_arr);
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// 非递归归并排序
void MergeSortNoR(int *arr, int n) {
    int *_arr = (int *) malloc(sizeof(int) * n);

    int gap = 1; // 每组数据个数

    while (gap < n) {
        for (int i = 0; i < n; i += 2 * gap) {
            // [i,i+gap-1] gap [i+gap,i+2*gap-1]
            // 归并
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            // TODO:归并过程中有出现两种情况
            // 1.右半区间可能不存在
            if (begin2 >= n) {
                break;
            }
            // 2.右半区间算多了要修正
            if (end2 >= n) {
                end2 = n - 1;
            }


            int index = i;
            while (begin1 <= end1 && begin2 <= end2) {
                if (arr[begin1] < arr[begin2]) {
                    _arr[index++] = arr[begin1++];
                } else {
                    _arr[index++] = arr[begin2++];
                }
            }

            while (begin1 <= end1) {
                _arr[index++] = arr[begin1++];
            }

            while (begin2 <= end2) {
                _arr[index++] = arr[begin2++];
            }

            // 拷贝回去
            for (int j = i; j <= end2; ++j) {
                arr[j] = _arr[j];
            }
        }

        gap *= 2;
    }

    free(_arr);

}
// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

/**
 * TODO:基数排序（桶排序）
 *          123 45 12 9 88 43
 *          依次分别取个位、十位、百位来排序
 *              个位：12 123 43 45 88 9
 *              十位：9 12 123 43 45 88
 *              百位：9 12 43 45 88 123
 *     ~~了解思想即可
 */

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

// 非比较排序
/*
 * TODO:计数排序:思想很巧，适用范围具有局限性
 *      时间复杂度：O(N+range) 使用于范围集中的整形数据
 *      空间复杂度：O(range)
 */
void CountSort(int *arr, int n) {
    int max = arr[0], min = arr[0];
    for (int i = 0; i < n; ++i) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }

    int range = max - min + 1;

    int *count = (int *) malloc(sizeof(int) * range);
    memset(count, 0, sizeof(int) * range);

    for (int i = 0; i < n; ++i) {
        count[arr[i] - min]++;
    }

    int j = 0;
    for (int i = 0; i < range; ++i) {
        while (count[i]--) {
            arr[j++] = i + min;
        }
    }
}

/**
 * TODO: 1.插冒归，它很稳
 *       2.选冒插，插完就方了 == O(N^2)
 *       3.快归堆，三N佬 == O(N*logN)
 */

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

void TestBubbleSort() {
    int arr[] = {3, 5, 2, 7, 8, 6, 1, 9, 4};
    BubbleSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestInsertSort() {
    int arr[] = {3, 5, 2, 7, 8, 6, 1, 9, 4};
    InsertSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestShellSort() {
    int arr[] = {3, 5, 2, 7, 8, 6, 1, 9, 4};
    ShellSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestSelectSort() {
    int arr[] = {9, 5, 2, 7, 8, 6, 1, -1, 4};
    SelectSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestHeapSort() {
    int arr[] = {3, 5, 2, 7, 8, 6, 1, 9, 4};
    HeapSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestQuickSort() {
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    QuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestNewQuickSort() {
    int arr[] = {53, 38, 65, 97, 76, 13, 27, 49};
    newQuickSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestQuickSortNoR() {
    int arr[] = {53, 38, 65, 97, 76, 13, 27, 49};
    QuickSortNoR(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestMergeSort() {
    int arr[] = {53, 38, 65, 97, 76, 13, 27, 49};
    MergeSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestMergeSortNoR() {
    int arr[] = {53, 38, 65, 97, 76, 13, 27, 49};
    MergeSortNoR(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

void TestCountSort() {
    int arr[] = {53, 38, 38, 97, 38, 13, 27, 49};
    CountSort(arr, sizeof(arr) / sizeof(int));
    PrintArray(arr, sizeof(arr) / sizeof(int));
}

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

// 测试排序的性能对比

// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
// ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————


int main() {
//    TestBubbleSort();
//    TestInsertSort();
//    TestShellSort();
//    TestHeapSort();
//    TestSelectSort();
//    TestQuickSort();
//    TestNewQuickSort();
//    TestQuickSortNoR();
//    TestMergeSort();
//    TestMergeSortNoR();
    TestCountSort();

    return 0;
}

